package com.javabasic.algorithm.leetcode;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2022/6/17 22:15
 */
public class DuplicateZeros {

    /**
     * 申请额外内存+重写
     * @param arr
     */
    public void duplicateZeros(int[] arr) {
        int len = arr.length;
        int newLen = len;
        for (int i = 0; i < len; i++) {
            if (arr[i] == 0) {
                newLen++;
            }
        }

        if (newLen == len) {
            return;
        }

        int[] newArr = new int[newLen];
        int tag = newLen - 1;
        for (int i = len-1; i >= 0; i--) {
            newArr[tag--] = arr[i];
            if (arr[i] == 0) {
                newArr[tag--] = arr[i];
            }
        }

        for (int i = 0; i < len; i++) {
            arr[i] = newArr[i];
        }
    }


    /**
     * 在原有内存地址移动数组内容
     * @param arr
     */
    public void duplicateZeros2(int[] arr) {
        int len = arr.length;
        int sumZero = 0;
        int targetIndex = -1;

        boolean targetIsZeroAndOutOfBound = false;
        for (int i = 0; i < len; i++) {
            if (arr[i] == 0) {
                sumZero++;
            }
            if (i + sumZero == len-1) {
                targetIndex = i;
                break;
            }
            if (i + sumZero >= len-1) {
                targetIndex = i;
                targetIsZeroAndOutOfBound = true;
                break;
            }
        }
        if (targetIndex == len-1) {
            return;
        }

        int tag = len-1;
        for (int index = targetIndex; index >= 0; index--) {
            arr[tag--] = arr[index];
            if (arr[index] == 0 && !targetIsZeroAndOutOfBound) {
                arr[tag--] = arr[index];
            }
            targetIsZeroAndOutOfBound = false;
        }
    }
}
